package com.sicheng.lc.杂题.路径问题;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/17 12:36
 */
public class 获取所有钥匙的最短路径 {
    //https://leetcode.cn/problems/shortest-path-to-get-all-keys/
    int m, n, i, j;


    static boolean[][][] visit = new boolean[30][30][1 << 6];

    {
        for (boolean[][] ints : visit) {
            for (boolean[] a : ints) {
                Arrays.fill(a, false);
            }
        }
    }

    public int shortestPathAllKeys(String[] grid) {
        m = grid.length;
        n = grid[0].length();
        int k = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') {
                    this.i = i;
                    this.j = j;
                } else if (c >= 'a' && c <= 'z') {
                    k++;
                }
            }
        }

        return bfs(grid, k);
    }

    static int[][] d = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };

    private int bfs(String[] grid, int k) {
        ArrayDeque<int[]> deque = new ArrayDeque<>();
        deque.offer(new int[]{i, j, 0, 0});
        visit[i][j][0] = true;
        int step = 0;
        while (!deque.isEmpty()) {
            step++;
            int size = deque.size();
            for (int l = 0; l < size; l++) {
                int[] p = deque.poll();
                for (int[] dd : d) {
                    assert p != null;
                    int x = p[0] + dd[0];
                    int y = p[1] + dd[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        // (i,j)->(x,y) 最基本的就是不越界且不是墙
                        char c = grid[x].charAt(y);
                        if (c == '#') continue;
                        int ck = p[2];
                        int keys = p[3];

                        // 当再次访问(x,y)时状态得不同
                        // 有可能发生第一次访问没有钥匙,下一次有钥匙就可以拓展结点的情况
                        // 下一次再次访问(x,y)并没有获取新状态就没得资格拓展(x,y)，这样只会增加路径长度徒劳无功
                        if (!visit[x][y][keys]) {

                            if (c >= 'a' && c <= 'z') {
                                // 遇到钥匙必须判断一下这个钥匙我之前有没得获取过
                                if ((keys >> (c - 'a') & 1) == 0) {
                                    keys |= 1 << (c - 'a');
                                    ck++;
                                }
                                if (ck == k)
                                    return step;

                            } else if (c >= 'A' && c <= 'Z') {
                                // 遇到锁时必须携带配对的钥匙
                                if ((keys >> (c + 32 - 'a') & 1) == 0) {
                                    continue;
                                }
                            }
                            visit[x][y][keys] = true;
                            deque.offer(new int[]{x, y, ck, keys});
                        }
                    }
                }
            }
        }
        return -1;

    }

    public static void main(String[] args) {
        获取所有钥匙的最短路径 s = new 获取所有钥匙的最短路径();
        String[] g = {"@..ab", "##B##", "....c"};
        System.out.println(s.shortestPathAllKeys(g));
    }
}
